package com.demo.java.OD301_350.OD348;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【完全二叉树非叶子部分后序遍历(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146163145
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入并将其转换为数组
        String[] input = scanner.nextLine().split(" ");
        int[] arr = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }

        // 输出层序遍历的结果
        System.out.println(solveMethod(arr));
    }

    // 深度优先搜索（DFS）层序遍历
    public static void dfs(int[] arr, int root, List<Integer> res) {
        int left = root * 2 + 1;  // 左子节点的索引
        int right = root * 2 + 2; // 右子节点的索引

        if (arr.length > left) {
            dfs(arr, left, res); // 递归处理左子节点
            if (arr.length > right) {
                dfs(arr, right, res); // 递归处理右子节点
            }
            res.add(arr[root]); // 将当前节点添加到结果列表
        }
    }

    // 解决方法，返回层次遍历的结果
    public static String solveMethod(int[] arr) {
        if (arr.length == 1) {
            return Integer.toString(arr[0]); // 如果只有一个节点，直接返回该节点
        }

        List<Integer> res = new ArrayList<>();
        dfs(arr, 0, res); // 从根节点（索引0）开始遍历

        // 将结果列表转换为字符串，并返回
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < res.size(); i++) {
            if (i > 0) {
                sb.append(" "); // 用空格分隔
            }
            sb.append(res.get(i)); // 添加节点到字符串
        }
        return sb.toString(); // 返回最终结果
    }
}